#include "string_array.h"
#include <cstring>
#include <iostream>

using namespace std;

//字符串初始化
myStr::myStr(const char* str)
{
    length=strlen(str);
    data=new char[length+1];    //总长度为字符数量+'\0'
    strcpy(data,str);
    next=new int[length];     //初始化KMP next数组
    nextVal=new int[length];  //初始化KMP nextVal数组
}

//字符串销毁
myStr::~myStr()
{
    //将三个数组释放
    delete[] data;
    delete[] next;
    delete[] nextVal;
}

//返回字符串长度
int myStr::get_length() const
{
    return length;
}

//获取字符串数据
const char* myStr::get_data() const
{
    return data;
}

//串的替换
bool replaceStr(myStr& S,const int& start,const myStr& T,const myStr& V)
{
    /*
    在主串S中，从位置start开始查找是否存在子串T
    若主串S中存在子串T，则用子串V替换子串T，且函数返回1
    若主串S中不存在子串T，则函数返回0， start取值从1开始
    */
   //检查start值是否合法
    if(start<1||start>S.length-T.length+1)
    {
        return false;
    }
    int position=simpleMatch(S,T);
    if(position!=-1&&position>=start)
    {
        //满足条件，进行替换操作
        char* new_data=new char[S.length-T.length+V.length+1];
        strncpy(new_data,S.data,position-1);
        strcpy(new_data+position-1,V.data);
        strcpy(new_data+position+V.length-1,S.data+position+T.length-1);

        delete[] S.data;
        S.data=new_data;
        S.length=S.length-T.length+V.length;
        return true;
    }
    return false;
}

int simpleMatch(const myStr& S,const myStr& T)
{
    for(int i=0;i<=S.get_length();i++)
    {
        if(strncmp(S.get_data()+i,T.get_data(),T.get_length())==0)
        {
            return i+1;       //返回位置
        }
    }
    return -1;              //未找到
}

//KMP辅助数组next的计算
void myStr::kmp_next()
{
    next[0]=0;
    next[1]=1;
    for(int i=0;i<length-2;i++)
    {
        int max=1;
        for(int j=1;j<i+2;j++)
        {
            if(strncmp(data,data+i+2-j,j)==0)
            {
                int temp=j+1;
                if(temp>max)
                {
                    max=temp;
                }
            }
        }
        next[i+2]=max;
    }
}

//KMP辅助数组nextVal的计算
void myStr::kmp_nextVal()
{
    nextVal[0]=0;
    for(int i=1;i<length;i++)
    {
        if(data[i]==data[next[i]-1])
        {
            nextVal[i]=next[next[i]-1];
        }
        else
        {
            nextVal[i]=next[i];
        }
    }
}

//KMP算法的字符串匹配算法
int kmpMatch(const myStr& S,const myStr& T)
{
    if(T.get_length()==0)   return 0;
    int j=0;
    for(int i=0;i<S.get_length();i++)
    {
        while(j>0&&S.data[i]!=T.data[j])
        {
            j=T.next[j-1];
        }
        if(S.data[i]==T.data[j])    j++;
        if(j==T.get_length())
        {
            return i-T.get_length()+2;
        }
    }
    return -1;
}

void myStr::print(){
    for(int i = 0; i < this->length; i++)
        cout << this->data[i];

    cout << endl;
}

void myStr::printNext(){
    for(int i = 0; i < length; i++)
        cout << next[i];
    cout << endl;
}

void myStr::printNextVal(){
    for(int i = 0; i < length; i++)
        cout << nextVal[i];
    cout << endl;
}

//初始化稀疏矩阵
/*
 myMatrix (const int& rNum, const int& cNum, const int& nNum, const int*)
 参数依次为行数、列数、三元组元素个数、三元组初始化数据
 数组元素为3的倍数，每3个数一组，分别为（row，col，value）
*/
myMatrix::myMatrix(const int& rNum,const int& cNum,const int& nNum,const int* data)
    :rowNum(rNum),colNum(cNum),nodeNum(nNum)
{
    nodeList=new matrixNode[nNum];
    for(int i=0;i<nNum;++i)
    {
        nodeList[i].row=data[i*3];
        nodeList[i].col=data[i*3+1];
        nodeList[i].value=data[i*3+2];
    }
    //使用插入排序进行排序
    insertSort();
}

//默认构造函数
myMatrix::myMatrix() :rowNum(0),colNum(0),nodeNum(0),nodeList(nullptr){}

//拷贝构造函数
myMatrix::myMatrix(const myMatrix& other)
    :rowNum(other.rowNum),colNum(other.colNum),nodeNum(other.nodeNum)
{
    if(nodeNum>0)
    {
        nodeList=new matrixNode[nodeNum];
        for(int i=0;i<nodeNum;++i)
        {
            nodeList[i]=other.nodeList[i];
        }
    }
    else
    {
        nodeList=nullptr;
    }
}

//销毁稀疏矩阵
myMatrix::~myMatrix()
{
    delete[] nodeList;
}

//插入排序
void myMatrix::insertSort()
{
    for(int i=1;i<nodeNum;++i)
    {
        matrixNode key=nodeList[i];
        int j=i-1;

        //将大于key的元素移动到后面
        while(j>=0&&(nodeList[j].row>key.row ||
            (nodeList[j].row==key.row &&nodeList[j].col>key.col)))
            {
                nodeList[j+1]=nodeList[j];
                j--;
            }
        nodeList[j+1]=key;
    }
}

void myMatrix::printMatrix(){
    cout << rowNum << "," << colNum << "," << nodeNum << endl;

    for(int i = 0; i < nodeNum; i++)
        cout << nodeList[i].row << "," << nodeList[i].col << "," << nodeList[i].value << endl;
}

//实现快速转置算法
void myMatrix::FastTransposeSMatrix(myMatrix& T)
{
    //设置转置矩阵行数和列数
    T.rowNum=colNum;
    T.colNum=rowNum;
    T.nodeNum=nodeNum;

    if(nodeNum>0)
    {
        T.nodeList=new matrixNode[nodeNum];

        int* rowCount=new int[colNum]();    //每列非零元素个数
        int* rowStart=new int[colNum+1];    //每列起始位置

        //统计每列的非零元素个数
        for(int i=0;i<nodeNum;++i)
        {
            rowCount[nodeList[i].col]++;
        }

        //计算每列起始位置
        rowStart[0]=0;
        for(int i=1;i<=colNum;i++)
        {
            rowStart[i]=rowStart[i-1]+rowCount[i-1];
        }

        //进行转置
        for(int i=0;i<nodeNum;++i)
        {
            int j=rowStart[nodeList[i].col]++;
            T.nodeList[j].row=nodeList[i].col;
            T.nodeList[j].col=nodeList[i].row;
            T.nodeList[j].value=nodeList[i].value;
        }
        delete[] rowCount;
        delete[] rowStart;
    }
    else
    {
        T.nodeList=nullptr;
    }
}